package com.learn.algorlthm;


import java.util.*;

/**
 * @classname:
 * @Description: 从上往下打印二叉树
 * @author: yfpu(fengpu.yang @ ucarinc.com)
 * @Date: 2018-07-31 19:49
 * 题目描述：
 *  从上往下打印出二叉树的每个节点，同层节点从左至右打印。
 */
public class Learn32_1 {


    public static void printTree() {
        TreeNode treeNode = getTreeNode();

        List<TreeNode> list = new ArrayList<>();
        list.add(treeNode);

        int length = list.size();
        for (int i = 0; i < length; i++) {
            TreeNode root = list.get(i);
            if (root.left != null)
                list.add(root.left);

            if (root.right != null)
                list.add(root.right);

            if (root.left != null || root.right != null)
                length++;

        }

        for (TreeNode node : list) {
            System.out.print(node.value + " ,");
        }

    }


    public static TreeNode getTreeNode() {
        int[] values = {1 ,2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 ,18, 19, 20};
//        int[] values = {1 ,2, 3, 4, 5, 6, 7};

        LinkedList<TreeNode> list = new LinkedList<>();
        for (int value : values) {
            list.add(new TreeNode(value));
        }

        for (int preIndex = 0; preIndex < values.length/2 -1; preIndex++) {

            TreeNode node = list.get(preIndex);
            node.left = list.get(preIndex *2 + 1);
            node.right = list.get(preIndex * 2 + 2);
        }

        int lastIndex = values.length/2 - 1;
        list.get(lastIndex).left = list.get(lastIndex * 2 +1);
        if (values.length % 2 != 0)
            list.get(lastIndex).right = list.get(lastIndex * 2 +2);


        return list.get(0);
    }


    static class TreeNode{
        public Integer value;

        public TreeNode left;
        public TreeNode right;

        public TreeNode() {
        }

        public TreeNode(Integer value) {
            this.value = value;
        }
    }
}
